import java.util.LinkedList;

public class Test {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {

        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public ListNode detectCycle(ListNode head) {
        //环形链表二
        //https://leetcode.cn/problems/linked-list-cycle-ii/
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //这里相等的时候，slow和fast可能不是在需要返回的节点，可能在这个节点之后，还没到入口的时候它们就在环里相遇了
            //所以这里我们要退出当相等的时候。
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        //我们再次把slow从头开始走，fast从相遇的节点开始走，当它们再次相遇的时候就是入口点
        //这里呢我们的fast和slow都是一步一步走的
        slow = head;
        while(slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    public boolean hasCycle(ListNode head) {
        //环形链表
        //https://leetcode.cn/problems/linked-list-cycle/description/
        if (head == null || head.next == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
            slow = slow.next;
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //相交链表
        //https://leetcode.cn/problems/intersection-of-two-linked-lists/
//        ListNode hA = headA;
//        ListNode hB = headB;
//        int l1 = 0;
//        int l2 = 0;
//        while(hA != null) {
//            l1++;
//            hA = hA.next;
//        }
//        while(hB != null) {
//            l2++;
//            hB = hB.next;
//        }
//        hA = headA;
//        hB = headB;
//        int ln = l1 - l2;
//        while(l1 != l2) {
//            if (l1 < l2) {
//                ln = l2 - l1;
//                while(ln != 0) {
//                    hB = hB.next;
//                    ln--;
//                    l2--;
//                }
//            }else {
//                while (ln != 0) {
//                    hA = hA.next;
//                    ln--;
//                    l1--;
//                }
//            }
//        }
//        while(hA != hB) {
//            hA = hA.next;
//            hB = hB.next;
//        }
//        if (hA == null) {
//            return null;
//        }
//        return hA;
        //求链表的长度
        ListNode hA = headA;
        ListNode hB = headB;
        int l1 = 0;
        int l2 = 0;
        while(hA != null) {
            l1++;
            hA = hA.next;
        }
        while(hB != null) {
            l2++;
            hB = hB.next;
        }

        //这里走完后，hA和hB为null，我们要重新赋值
        hA = headA;
        hB = headB;

        //求差值
        int ln = l1 - l2;
        if (ln < 0) {
            //我们在这里使每次长的都是hA，每次短的都是hB、
            hA = headB;
            hB = headA;
            ln = l2 - l1;
        }

        //让长的链表先走ln步，是其两个链表同步
        while (ln != 0) {
            hA = hA.next;
            ln--;
        }

        //我们把hA和hB一起移动，当我们的hA和hB相遇的时候就是相交的节点
        while (hA != hB) {
            hA = hA.next;
            hB = hB.next;
        }

        //判断hA或者hB如果为null就没有相交
        if (hA == null) {
            return null;
        }

        //返回相交的节点
        return hA;
    }
    public boolean chkPalindrome(ListNode head) {
        //回文链表
        //https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
        //双指针法：快慢指针法
        if (head == null ) {
            return true;
        }
        //找中间节点，slow就是中间节点。
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //翻转中间节点后面的链表
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        //判断是否回文
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            //这里需要判断一下偶数的情况下
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    public ListNode partition(ListNode pHead, int x) {
        //链表分割
        //https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
        ListNode smallHead = null;
        ListNode smallLast = null;
        ListNode bigHead = null;
        ListNode bigLast = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (smallHead == null) {
                    //第一次删除的时候
                    smallHead = smallLast = cur;
                }else {
                    smallLast.next = cur;
                    smallLast = smallLast.next;
                }
            }else {
                if (bigHead == null) {
                    bigHead = bigLast = cur;
                }else {
                    bigLast.next = cur;
                    bigLast = bigLast.next;
                }
            }
            cur = cur.next;
        }
        if (smallHead == null) {
            return bigHead;
        }
        smallLast.next = bigHead;
        if (bigLast != null) {
            bigLast.next = null;
        }
        return smallHead;
//        ListNode smallx = new ListNode(-1);
//        ListNode sx = smallx;
//        ListNode bigx = new ListNode(-1);
//        ListNode bx = bigx;
//        while (pHead != null) {
//            if (pHead.val < x) {
//                sx.next = pHead;
//                pHead = pHead.next;
//                sx = sx.next;
//            }else {
//                bx.next = pHead;
//                pHead = pHead.next;
//                bx = bx.next;
//            }
//        }
//        if(smallx == null) {
//            return bigx.next;
//        }
//
//        if (bigx != null) {
//            bx.next = null;
//        }
//        sx.next = bigx.next;
//        return smallx.next;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //合并两个有序的链表
        //https://leetcode.cn/problems/merge-two-sorted-lists/
        ListNode newList = new ListNode();
        ListNode prev = newList;
        while(list1 != null && list2 != null) {
            if (list2.val <= list1.val) {
                prev.next = list2;
                list2 = list2.next;
            }else {
                prev.next = list1;
                list1 = list1.next;
            }
            prev = prev.next;
        }
        if (list1 != null) {
            prev.next = list1;
        }
        if (list2 != null) {
            prev.next = list2;
        }

        return newList.next;
    }
    public int kthToLast(ListNode head, int k) {
        //返回倒数第k个节点
        //https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/?envType=problem-list-v2&envId=linked-list
        ListNode fast = head;
        ListNode slow = head;
        //2:
        while(k - 1 > 0) {
            fast = fast.next;
            k--;
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //1：
//        while(k > 0) {
//            fast = fast.next;
//            k--;
//        }
//        while(fast != null) {
//            fast= fast.next;
//            slow = slow.next;
//        }
        return slow.val;
    }
    public static ListNode middleNode(ListNode head) {
        //链表的中间节点
        //https://leetcode.cn/problems/middle-of-the-linked-list/
        if (head == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }
    public static ListNode reverseList(ListNode head) {
        //反转链表
        //https://leetcode.cn/problems/reverse-linked-list/submissions/
        //先判断链表是否为空
        if (head == null) {
            return head;
        }

        //开始头插
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            //保存cur的下一个节点
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
    public static ListNode removeElements (ListNode head, int val) {
        //删除链表中所有的val值的节点
        //https://leetcode.cn/problems/remove-linked-list-elements/description/
        if (head == null) {
            return head;
        }
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            if (cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //判断head的val是否和val相等
        if (head.val == val) {
            head = head.next;
        }
        return head;
    }
}
